翻訳と辞書 Words near each other ・ Hard Wired ・ HARD with STYLE ・ Hard Work ・ Hard Workin' Man ・ Hard Workin' Man (song) ・ Hard Working Americans ・ Hard Working Americans (album) ・ Hard Working Class Heroes ・ Hard Works ・ Hard X-ray Modulation Telescope ・ Hard, Austria ・ Hard, Fast and Beautiful ・ Hard, Hard Times ・ Hard-Boiled Wonderland and the End of the World ・ Hard-clad silica optical fiber ・ Hard-core predicate ・ Hard-court specialist ・ Hard-edge painting ・ Hard-Fi ・ Hard-Fi discography ・ Hard-Hat Domo ・ Hard-Ons ・ Hard-paste porcelain ・ Hard-surface cleaner ・ Hard-tail ・ Harda ・ Harda district ・ Harda twin train derailment ・ Hardacre Film Festival ・ Hardaker Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Hard-core predicate ： ウィキペディア英語版 Hard-core predicate In cryptography, a hard-core predicate of a one-way function ''f'' is a predicate ''b'' (i.e., a function whose output is a single bit) which is easy to compute given ''x'' but is hard to compute given ''f(x)''. In formal terms, there is no probabilistic polynomial-time algorithm that computes ''b(x)'' from ''f(x)'' with probability significantly greater than one half over random choice of ''x''.〔Goldwasser, S. and Bellare, M. ("Lecture Notes on Cryptography" ). Summer course on cryptography, MIT, 1996-2001〕 A hard-core function can be defined similarly. A hard-core predicate captures "in a concentrated sense" the hardness of inverting ''f''. While a one-way function is hard to invert, there are no guarantees about the feasibility of computing partial information about the preimage ''c'' from the image ''f(x)''. For instance, while RSA is conjectured to be a one-way function, the Jacobi symbol of the preimage can be easily computed from that of the image.〔 It is clear that if a one-to-one function has a hard-core predicate, then it must be one way. Oded Goldreich and Leonid Levin (1989) showed how every one-way function can be trivially modified to obtain a one-way function that has a specific hard-core predicate.〔O. Goldreich and L.A. Levin, (A Hard-Core Predicate for all One-Way Functions ), STOC 1989, pp25–32.〕 Let ''f'' be a one-way function. Define :''g(x, r)'' = ''(f(x), r)'', where the length of ''r'' is the same as that of ''x''. Let $x\_j$ denote the ''j''th bit of ''x'' and $r\_j$ the ''j''th bit of ''r''. Then :$b(x,\; r)\; =\; \backslash bigoplus\_j\; x\_j\; r\_j$ is a hard core predicate of ''g''. Note that $b(x,r)\; =\; \backslash langle\; x,\; r\; \backslash rangle$ where $\backslash langle\; \backslash cdot,\; \backslash cdot\; \backslash rangle$ denotes the standard inner product on the vector space $(\backslash Z/2\backslash Z)^n$. This predicate is hard-core due to computational issues; that is, it is not hard to compute because ''g(x, r)'' is information theoretically lossy. Rather, if an algorithm exists to compute this predicate efficiently, then an algorithm exists to invert ''f'' efficiently. A similar construction yields a hard-core function with ''log (|x|)'' output bits. It is sometimes the case that an actual bit of the input ''x'' is hard-core. For example, every single bit of inputs to the RSA function is a hard-core predicate of RSA and blocks of $O(\backslash log\; |x|)$ bits of x are indistinguishable from random bit strings in polynomial time (under the assumption that the RSA function is hard to invert).〔J. Håstad, M. Naslund, (The Security of all RSA and Discrete Log Bits (2004) ): Journal of the ACM (JACM), 2004.〕 Hard-core predicates give a way to construct a pseudorandom generator from any one-way permutation. If ''b'' is a hard-core predicate of a one-way permutation ''f'', and ''s'' is a random seed, then :$\backslash left\; \backslash \_n$ is a pseudorandom bit sequence.〔 Hard-core predicates of trapdoor one-way permutations (known as trapdoor predicates) can be used to construct semantically secure public-key encryption schemes.〔 ==See also== * List-decoding (describes list decoding; the core of the Goldreich-Levin construction of hard-core predicates from one-way functions can be viewed as an algorithm for list-decoding the Hadamard code). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hard-core predicate」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.